package org.apache.commons.graph.collections

import org.hamcrest.CoreMatchers
import org.junit.After
import org.junit.Assert
import org.junit.Before
import org.junit.Test
import java.util.*

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 * The [FibonacciHeap] test case taking inspiration from
 * [Test-Driving a Heap-Based Priority Queue](http://langrsoft.com/jeff/2011/11/test-driving-a-heap-based-priority-queue/)
 */
class FibonacciHeapTestCase {
    private var queue: FibonacciHeap<Int>? = null

    @Test(expected = NoSuchElementException::class)
    fun elementThrowsException() {
        queue!!.element()
    }

    @Before
    fun setUp() {
        queue = FibonacciHeap<Int>()
    }

    @After
    fun tearDown() {
        queue = null
    }

    @Test
    fun testAddAllAndContinsItem() {
        val c: MutableCollection<Int> = ArrayList()

        c.add(50)
        c.add(100)
        c.add(20)
        c.add(21)

        queue!!.addAll(c)

        Assert.assertThat(queue!!.isEmpty(), CoreMatchers.`is`(false))
        Assert.assertThat(queue!!.containsAll(c), CoreMatchers.`is`(true))

        Assert.assertThat(queue!!.contains(100), CoreMatchers.`is`(true))
        Assert.assertThat(queue!!.contains(21), CoreMatchers.`is`(true))
        Assert.assertThat(queue!!.contains(50), CoreMatchers.`is`(true))
        Assert.assertThat(queue!!.contains(20), CoreMatchers.`is`(true))
    }

    @Test
    fun testClearQueue() {
        val r = Random(System.currentTimeMillis())
        for (i in 0..999) {
            val number = r.nextInt(10000)
            queue!!.add(number)
        }

        Assert.assertThat(queue!!.isEmpty(), CoreMatchers.`is`(false))
        queue!!.clear()
        Assert.assertThat(queue!!.isEmpty(), CoreMatchers.`is`(true))
    }

    @Test
    fun testEmptyWhenCreated() {
        Assert.assertThat(queue!!.isEmpty(), CoreMatchers.`is`(true))
        Assert.assertThat(queue!!.poll(), CoreMatchers.nullValue())
    }

    @Test
    fun testInsertSameValuesAndReturnsOrderedItems() {
        queue!!.add(50)
        queue!!.add(100)
        queue!!.add(50)

        Assert.assertThat(queue!!.poll(), CoreMatchers.`is`(50))
        Assert.assertThat(queue!!.poll(), CoreMatchers.`is`(50))
        Assert.assertThat(queue!!.poll(), CoreMatchers.`is`(100))
        Assert.assertThat(queue!!.isEmpty(), CoreMatchers.`is`(true))
    }

    @Test
    fun testInsertSingleItem() {
        queue!!.add(50)

        Assert.assertThat(queue!!.poll(), CoreMatchers.`is`(50))
        Assert.assertThat(queue!!.isEmpty(), CoreMatchers.`is`(true))
    }

    @Test
    fun testIsEmptyAfterSoleElementRemoved() {
        queue!!.add(50)
        queue!!.poll()

        Assert.assertThat(queue!!.isEmpty(), CoreMatchers.`is`(true))
    }

    @Test
    fun testNoLongerEmptyAfterAdd() {
        queue!!.add(50)

        Assert.assertThat(queue!!.isEmpty(), CoreMatchers.`is`(false))
    }

    @Test
    fun testOfferPeekAndElement() {
        queue!!.offer(50)
        queue!!.offer(100)
        queue!!.offer(20)
        queue!!.offer(21)

        Assert.assertThat(queue!!.isEmpty(), CoreMatchers.`is`(false))
        Assert.assertThat(queue!!.peek(), CoreMatchers.`is`(20))
        Assert.assertThat(queue!!.element(), CoreMatchers.`is`(20))
        Assert.assertThat(queue!!.size, CoreMatchers.`is`(4))
    }

    @Test
    fun testReturnsOrderedItems() {
        queue!!.add(100)
        queue!!.add(50)

        Assert.assertThat(queue!!.poll(), CoreMatchers.`is`(50))
        Assert.assertThat(queue!!.poll(), CoreMatchers.`is`(100))
        Assert.assertThat(queue!!.isEmpty(), CoreMatchers.`is`(true))
    }

    @Test
    fun testReturnsOrderedItemsFromRandomInsert() {
        val r = Random(System.currentTimeMillis())
        val expected: MutableList<Int> = ArrayList()

        for (i in 0..999) {
            val number = r.nextInt(10000)
            expected.add(number)

            queue!!.add(number)
        }
        Collections.sort(expected)

        for (integer in expected) {
            val i = queue!!.poll()
            Assert.assertThat(i, CoreMatchers.`is`(integer))
        }

        Assert.assertThat(queue!!.isEmpty(), CoreMatchers.`is`(true))
    }

    @Test
    fun testSingletonQueueReturnsSoleItemOnPoll() {
        queue!!.add(50)

        Assert.assertThat(queue!!.poll(), CoreMatchers.`is`(50))
    }
}
